package special;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

public class LRUCache2 {
    static class Node{
        int key;
        int value;
        Node(int key, int value){
            this.key = key;
            this.value = value;
        }
    }
    public int capacity;
    public Map<Integer, Node> map;
    LinkedList<Node> list = new LinkedList<>();

    public LRUCache2(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>();
    }

    public int get(int key) {
        if (map.containsKey(key)){
            Node node = map.get(key);
            changeFirst(node);
            return node.value;
        }
        return -1;
    }

    public void put(int key, int value) {
        if (list.size() == capacity){
            if (map.containsKey(key)){
                Node node = map.get(key);
                node.value = value;
                changeFirst(node);
            }else {
                Node node = new Node(key, value);
                map.remove(list.getLast().key);
                list.removeLast();
                list.addFirst(node);
                map.put(key, node);
            }
            return;
        }
        if (map.containsKey(key)){
            Node node = map.get(key);
            node.value = value;
            changeFirst(node);
        }else {
            Node node = new Node(key, value);
            list.addFirst(node);
            map.put(key, node);
        }
    }

    private void changeFirst(Node node) {
        list.remove(node);
        list.addFirst(node);
    }
}
